import java.util.List;

/**
 * 面试题 08.06. 汉诺塔问题
 * https://leetcode.cn/problems/hanota-lcci/description/
 */
class Solution {
    public void hanota(List<Integer> a, List<Integer> b, List<Integer> c) {
        //dfs(a, b, c, a.size());
        //不讲武德，笔试可用
        for(int x : a) c.add(x);
    }
    public void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {
        if(n == 1) {
            c.add(a.remove(a.size() - 1));
            return;
        }
        dfs(a, c, b, n - 1);
        c.add(a.remove(a.size() - 1));
        dfs(b, a, c, n - 1);
    }
}